The present invention relates to a deinterleaver for deinterleaving data that has been transmitted in an interleaved format.
It is common practice in communications equipment, data storage devices, etc. to interleave transmitted data for suppressing burst errors produced in data transfer and to restore the data at the receiver by use of a deinterleaver.
The following interleaving/deinterleaving technique is known in the art. As shown in FIG. 6, with respect to interleaved data, 32 bits of data comprise a word, and 32 words (1024 bits) comprise a block. In each block, each word is separated into four phases a-d, and data is multiplexed so that words with four alternating phases are arranged. In transmitting data, bit lines and word lines are interchanged to interleave a block of data. In particular, each data item as shown in FIG. 6 is identified by [phase name], [word number], and ([bit number]). After the interleaving process is completed, data is transmitted, 1 bit at a time, in the order a0(0) , b0(0) , c0(0) , d0(0) , a1(0) , . . . , d6(31), a7(31), b7(31), c7(31), d7(31).
Data interleaved in the above matter have been deinterleaved by a deinterleaver having the following structure. The deinterleaver is comprised of a first 1024-bit RAM permitting data to be read and written, 1 bit at a time, to interchange bit lines and word lines; a second 1024-bit RAM for separation of phases; and the respective address counters for the first RAM and second RAM. Let RA[9, 8, 7, 6, 5) be the higher significant 5-bit address lines for specifying higher significant addresses of the 1024 bits in the first RAM permitting data to be read and written, 1 bit at a time, and RA[4, 3, 2, 1, 0] be the lower significant 5-bit address lines for specifying lower significant addresses. The output from the address counter consisting of 10 bits for addressing is divided into higher significant 5 bits and lower significant 5 bits, which are indicated by CA[9, 8, 7, 6, 5] and CA[4, 3, 2, 1, 0], respectively. For convenience, RA[9, 8, 7, 6, 5] is given by RA[9:5].
The higher significant 5-bit output CA[9:5] and the lower significant 5 bit output CA[4:0] can be alternately coupled to the address lines RA[9:5] and RA[4:0] by selectors. Thus, whenever writing of a block of data is completed, the higher significant 5-bit output and the lower significant 5-bit output from the address counter are interchanged and the data written to RAM is read out. Every subsequent block written to RAM is directly written into the address from which data has been just read out. Consequently, bit lines and word lines are interchanged.
Specifically, with respect to the first block, the higher significant 5-bit output and the lower significant 5-bit output from the address counter are not interchanged and written without modification as illustrated in FIG. 7. In this figure, the rows indicate higher significant addresses 0-31 in the RAM specified by the higher significant 5-bit output from the address counter and the columns indicate lower significant addresses 0-31 specified by the lower significant 5-bit output. For convenience, the higher and lower significant addresses are represented in decimal notation and in the description given below, decimal notation is also used. Similar rules are applied to the addresses in the storage device specified by higher and lower significant addresses. With respect to the first block, writing is done in the direction of rows. As a result, data is written into the RAM while interchanging the word lines and bit lines of the original data format shown in FIG. 6. Then, the higher significant 5 bits and the lower significant 5 bits of the output from the address counter are interchanged and read out in the direction of columns. More specifically, with respect to the lower significant address 0 shown in FIG. 7, data is read out up to higher significant addresses 0-31. Then, with respect to lower significant address 1, data are read out up to higher significant addresses 0-31. In this way, data is read out up to the final lower significant address 31. The word lines and bit lines are again interchanged to regain the original data format shown in FIG. 6, in outputting data. One bit of data is output at a time in the order a0(0), a0(1), a0(31), b0(0), . . . , b0(31), c0(0), . . . , c0(31), d7(0), d7(31). Simultaneously with the reading, data in the second block is written, 1 bit at a time, into the address just read out. When the writing of the data in the second block is complete, a data array as shown in FIG. 8 is obtained. Subsequently, the higher significant bits and the lower significant bits of the output from the address counter are again interchanged and data is read out. Concurrently, data in the third block are written as it is into the address of the data just read.
Words with phases a-d cyclically appear at the output data of the RAM. It is necessary to perform phase separation (i.e., words must be rearranged according to each of the phases a-d). Therefore, an output consisting of an array of words with the alternating phases a-d is once stored in the second 1024-bit RAM in the same format as shown in FIG. 6. Then, the first four words are read by means of a separate address counter. Thus, all the words with the phase a are read out of RAM. Next, all the words with the phase b are read out. Similar reading operations are performed for the phases c and d. In consequence, phase separation is done. Hence, data is read, 1 bit at a time, from the second RAM in the order a0(0), a0(1), . . . , a0(31), a1(0), a1(31), . . . , a7(31), b0(0), . . . , b7(31), . . . , d7(31).
As described above, the prior art deinterleaver rearranges bit lines and word lines of data and then separates words according to the phases. Therefore, two RAMs for holding data and associated address counters have been required. For this reason, a memory having a capacity twice as large as the data amount of data in a block is required. Furthermore, a control unit for this memory is necessary. Consequently, the size of the deinterleaver is increased and its structure is complicated.
Accordingly, in the present invention, word lines and bit lines in each block where plural phases are cyclically assigned to each word are interchanged to deinterleave interleaved data. At this time, bit lines and word lines of the data are rearranged and simultaneous phase separation is performed in the manner described below.
A storage means has a storage area being a capacity corresponding to one block of data. The storage area has individual storage locations addressed by higher and lower significant addresses. Each bit of the above-described data is stored in each individual storage location in the storage means. Data is read, 1 bit at a time, from the storage means by specifying higher and lower significant addresses in turn. A newly incoming data item is written into the storage location just read out. Whenever a block of data is written, first and second count signals for specifying higher and lower significant addresses, respectively, are interchanged. At this time, a counting rule about the first and second count signals is cyclically changed as the phase is cyclically changed. In this manner, the word lines and bit lines are rearranged. A deinterleaved output is produced such that words are arranged according to phase. This can reduce the whole storage capacity to the amount of data corresponding to a block. Hence, the size of the apparatus can be reduced, and the structure can be simplified, thereby resulting in a highly cost-effective deinterleaver.
With a deinterleaver in accordance with the present invention, a word of data consists of 2n bits (n is an integer equal to or greater than 2), and a block consists of 2n words. In each block, plural phases are assigned to each word cyclically to form a first data row. In each word, a row from the first bit to the final bit is referred to as a bit line. In each block, a row from the first word to the final word is referred to as a word line. Each block is regarded as a matrix consisting of word lines and bit lines. The word lines and bit lines in each block are rearranged into a second data line. The deinterleaver deinterleaves this second data line and includes a storage means having storage locations for storing 22n bits of data and a control means. Each bit of data is identified by a higher significant address and a lower significant address which are formed by the higher significant n bits and the lower significant n bits, respectively, of 2n bits comprising an address. Each bit of data in the second data line is stored in each of the storage locations. The control means reads one bit of data at a time from the storage means by specifying the aforementioned higher and lower significant addresses.
The control means writes a newly incoming data in the second data line into the storage location from which data was just read out. Whenever one block of the second data line is written, signals for specifying the higher and lower significant addresses are interchanged and first and second count signals are interchanged as mentioned above. The counting rule is cyclically changed according to cycling of phase. The second data line is written into the storage means and read from it. In this way, a third data line obtained by rearranging the first data line such that words are arranged according to phase is produced.
The first data is obtained by separating each word into 2k phases cyclically in each block (k is an integer greater than 1 and less than n). The control means comprises a 2n-bit counter, a first selector means, and a second selector means. The first selector means receives the higher significant n bits of the output from the counter and produces the first counter signal in which the higher significant k bits of the higher significant n bits described above have been shifted into lower significant bits cyclically. The second selector means receives the lower significant n-bit output from the counter and produces the aforementioned second count signal in which the higher significant k bits of the lower significant n-bit output have been shifted into lower significant bits cyclically. The aforementioned shifts in the first and second count signals are preferably made alternately to modify the counting rule.
For example, each word is preferably comprised of 32 bits of data, and each block consists of 32 words. The first data line is obtained by separating each word into 4 phases cyclically in each block. The control means comprises a 10-bit counter, a first selector means, and a second selector means. The first selector means receives the higher significant 5 bit output from the counter and produces the first count signal in which the higher significant 2 bits of the received higher significant 5 bits have been shifted into lower significant bits cyclically. The second selector means receives the lower significant 5 bit-output from the counter and produces the second count signal in which the higher significant 2 bits of the lower significant 5 bits of the output have been shifted into lower significant bits cyclically. The aforementioned shifts in the first and second count signals are made alternately to modify the counting rule.
Other objects and features of the invention will appear in the course of the description thereof, which follows.